package hot100;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.Deque;

public class DailyTemperatures {
    //73,74,75,71,69,72,76,73
    //1,1,4,2,1,1,0,0
    public int[] dailyTemperatures(int[] temperatures) {
        //递减的栈，留在栈里的都已经是相对较大的，后面继续找这些更大的元素
        //比这些元素小的元素都已经出栈，并且出栈时都已经赋值
        int n = temperatures.length;
        int[] res = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.getLast()]) {
                int topIndex = stack.removeLast();
                res[topIndex] = i - topIndex;
            }
            stack.addLast(i);
        }

        return res;
    }

    @Test
    public void test() {
        int[] tempers = {73, 74, 75, 71, 69, 72, 76, 73};
        int[] ints = dailyTemperatures(tempers);
        for (int i = 0; i < ints.length; i++) {
            System.out.print(ints[i] + " ");
        }

    }
}
